The need to compress digital image data, whether static or dynamic images (i.e., video images) has dramatically increased. In particular, digital video data creates among the largest amounts of data utilized. For example, a single 8.5.times.11 inch, 24-bit color image at 100 dots-per-inch, is made up of over 22 million pixels of data. Data compression is utilized in multimedia computer systems, as well as in digital video devices (i.e., digital video camcorders, DVD) players, and digital still image cameras) to reduce memory requirements. The popularity of these digital devices has increased dramatically. In addition, compression is used to transmit digital broadcasts such as direct satellite broadcasts and High Definition Television (HDTV).
Typically, digital image data is transmitted or stored in a compressed format and decompressed prior to the display of the image. Examples of widely used compression techniques are those that comply with MPEG, MPEG-2 (Moving Pictures Expert Group), DV and JPEG point Photographic Experts Group) standards.
Given digital image data to be compressed, an encoder follows an ordered set of steps called an encoding process. The encoding process is not standardized, and typically varies as encoders of different complexities can be used in different applications. Many encoding processes (including those that comply with MPEG, MPEG-2, DV or JPEG standards) utilize quantization procedures to reduce storage requirements of digital image data and regulate its output bandwidth.
The process of quantization typically begins with the selection of a quantization table from a set of quantization tables. Each quantization table contains a set of quantization steps. The actual quantization process itself is well known and will not be discussed in detail herein. However, as a result of the quantization process, the size of image data representing the unquantized image is reduced. Furthermore, the size of the quantized data can be varied according to the quantization table selected. For example, the smaller the magnitude of a table's quantization steps, the greater the size of the quantized data used to represent the unquantized digital image. Similarly, the larger the magnitude of a table's quantization steps, the smaller the size of the quantized data used to represent the unquantized digital image. In other words, if a smaller image data size is required, quantization steps of larger magnitudes are used. Analogously, if a larger image data size is desired, quantization steps of smaller magnitude are utilized. For further information, see Introduction To Data Compression, Sayood, 1996, pages 169-254.
A problem with conventional quantization table selection techniques is when delays are introduced by the encoder when selecting a quantization table to utilize. For example, bursty delay may cause time latency. In addition, a constant delay by the encoder may cause the encoder to fail in real-time encoding.
A number of different searching techniques can be used to locate a quantization table, including linear and binary searching techniques. A linear search simply starts at a first location in a list of quantization tables and searches sequentially until the object of interest, i.e., a quantization table, is located. The amount of time required to perform a linear search is proportional to the size of a list. In contrast, a binary search technique assumes that the collection of elements has been ordered. An object at the center of the tree (identified as a root node) is selected and the relationship of that object to the object being sought is determined. If the object precedes or follows the object being sought, the results are used to bisect the search range and recursively continue the process. The amount of time required to perform a binary search is proportional to the height of the tree.
Although each of these searching techniques are useful, each has advantages and drawbacks. For example, a linear searching technique is fast when the object of interest is located near the starting point in the list since only a small number of comparisons need to be performed to locate it. However, in a worst case, when the object of interest is at the end of the list, the entire list must be traversed before the object is located. Additionally, although binary searching techniques typically provide an efficient method for searching large databases of objects (since the search space is cut in half during each iteration), such techniques are not as efficient when the object of interest is located close to the starting point of the search. In sum, the sole use of either searching technique to locate a quantization table containing quantization steps of desired magnitude can introduce delays into a digital device's data transmission rate. For the foregoing reason, there is a need for a methodology to rapidly locate a quantization table containing quantization steps of a desired magnitude.